home *** CD-ROM | disk | FTP | other *** search
/ ShareWare OnLine 2 / ShareWare OnLine Volume 2 (CMS Software)(1993).iso / infor / ddj_more.zip / TOOLS.C < prev    next >
Text File  |  1993-01-04  |  17KB  |  800 lines
  1. /*-----------------------------------------------------------------------
  2.  *
  3.  *    TOOLS.C:  The expression parser used by GREP
  4.  *
  5.  *
  6.  *            Copyright (c) 1984 Allen Holub
  7.  *
  8.  *    Permission to copy this program or any part of this program
  9.  *    is granted in the case of personal, non-commercial use only.
  10.  *    Any use for profit or other commercial gain without written
  11.  *    permission of the author is prohibited.
  12.  *
  13.  *    If you've been given this program by a friend, and you find
  14.  *    it worthwhile, I'd appreciate your sending $35 to me for the
  15.  *    program.
  16.  *
  17.  * Software Engineering Consultants, P.O. Box 5679, Berkeley CA, 94705
  18.  *
  19.  *-----------------------------------------------------------------------
  20.  */
  21.  
  22. /*
  23.  *    This module contains the various routines needed by grep 
  24.  *    to match regular expressions.  Routines are ordered
  25.  *    alphabetically.
  26.  */
  27.  
  28. #include <stdio.h>
  29. #include "tools.h"
  30.  
  31. char    *amatch( lin, pat, boln)
  32. char    *lin, *boln;
  33. TOKEN    *pat;
  34. {
  35.     /*    Scans through the pattern template looking for a match
  36.      * with lin.  Each element of lin is compared with the template
  37.      * until either a mis-match is found or the end of the template
  38.      * is reached.  In the former case a 0 is returned; in the latter,
  39.      * a pointer into lin (pointing to the last character in the
  40.      * matched pattern) is returned.
  41.      *
  42.      *    "lin"    is a pointer to the line being searched.
  43.      *    "pat"    is a pointer to a template made by makepat().
  44.      *    "boln"    is a pointer into "lin" which points at the 
  45.      *            character at the beginning of line.
  46.      */
  47.     
  48.     register char    *bocl, *rval, *strstart;
  49.     
  50.     if (pat == 0)
  51.         return ( (char*)0 );
  52.         
  53.     strstart = lin;
  54.     
  55.     while ( pat )
  56.     {
  57.         if (pat->tok == CLOSURE && pat->next)
  58.         {
  59.             /*
  60.              *    Process a closure:
  61.              *    First skip over the closure token to the
  62.              *    object to be repeated.  This object can be
  63.              *    a character class.
  64.              */
  65.              
  66.             pat = pat->next;
  67.             
  68.             /*    Now match as many occurrences of the
  69.              *    closure pattern as possible.
  70.              */
  71.             
  72.             bocl = lin;
  73.             
  74.             while ( *lin && omatch(&lin, pat, boln) )
  75.                 ;
  76.             
  77.             /*    'Lin' now points to the character that
  78.              *    made us fail.  Now go on to process the
  79.              *    rest of the string.  A problem here is
  80.              *    a character following the closure which
  81.              *    could have been in the closure.
  82.              *    For example, in the pattern "[a-z]*t" (which
  83.              *    matches any lower-case word ending in a t),
  84.              *    the final 't' will be sucked up in the while
  85.              *    loop.  So, if the match fails, we back up a 
  86.              *    notch and try to match the rest of the
  87.              *    string again, repeating this process
  88.              *    recursively until we get back to the 
  89.              *    beginning of the closure.  The recusion
  90.              *    goes, at most, two levels deep.
  91.              */
  92.             
  93.             if (pat = pat->next)
  94.             {
  95.                 while (bocl <= lin )
  96.                 {
  97.                     if (rval = amatch(lin, pat, boln) )
  98.                     {
  99.                         /* success */
  100.                         return(rval);
  101.                     }
  102.                     else
  103.                         --lin;
  104.                 }
  105.                 return (0);    /* match failed */
  106.             }
  107.         }
  108.         else if ( omatch(&lin, pat, boln) )
  109.         {
  110.             pat = pat->next;
  111.         }
  112.         else
  113.         {
  114.             return (0);
  115.         }
  116.     }
  117.     
  118.     /*
  119.      *    Note that omatch() advances lin to point at the next
  120.      *    character to be matched.  Consequently, when we reach
  121.      *    the end of the template, lin will be pointing at the 
  122.      *    character following the last character matched.
  123.      *    the exceptions are templates containing only a
  124.      *    BOLN or EOLN token.  In these cases omatch doesn't
  125.      *    advance.
  126.      *
  127.      *    So, decrement lin to make it point at the end of the
  128.      *    matched string.  Then, check to make sure that we haven't
  129.      *    decremented past the beginning of the string.
  130.      *
  131.      *    A philosophical pint should be mentioned here. Is $
  132.      *    a position or a character? (i.e., does $ mean the EOL
  133.      *    character itself or does it mean the character at the end of
  134.      *    the line.) I decided here to make it mean the former, in
  135.      *    order to make the behavior of amatch() consistent.  If you
  136.      *    give amatch a pattern ^$ (amtch all lines consisting only
  137.      *    of an end of line) then, since something has to be returned,
  138.      *    a pointer to the end of line character itself is returned.
  139.      *
  140.      *    The --lin is done outside the return statement because max()
  141.      *    is often a macro (which has side-effects).
  142.      */
  143.      
  144.     --lin;
  145.     return ( max(strstart, lin) );
  146. }
  147.  
  148. /*---------------------------------------------------------------------*/
  149.  
  150. #ifdef    DEBUG
  151.  
  152. delete( ch, str )
  153. int        ch;
  154. register char    *str;
  155. {
  156.     /*    Delete the first occurrence of character from string
  157.      *    moving everything else over a notch to fill the hole.
  158.      */
  159.     
  160.     ch &= 0xff;
  161.     
  162.     while ( *str && *str != ch)
  163.         str++;
  164.     while ( *str ) 
  165.     {
  166.         *str = *(str + 1);
  167.         str++;
  168.     }
  169. }
  170.  
  171. #endif
  172.  
  173. /*----------------------------------------------------------------------*/
  174.  
  175. setbit( c, field )
  176. int    c;
  177. char    field[];
  178. {
  179.     /*    Set a bit in the bit ASCII bit map corresponding to the
  180.      *    character c.  Field must be at least 16 bytes long.
  181.      */
  182.     
  183.     field[ (c & 0x7f) >> 3 ] |= 1 << (c & 0x07) ;
  184. }
  185.  
  186. /*---------------------------------------------------------------------*/
  187.  
  188. testbit( c, field)
  189. int    c;
  190. char    field[];
  191. {
  192.     /*    See if the bit corresponding to c in field is set.
  193.      */
  194.     
  195.     return ( field[ (c & 0x7f) >> 3] & (1 << (c & 0x07))  );
  196. }
  197.  
  198. /*----------------------------------------------------------------------*/
  199.  
  200. char    *dodash( delim, src, map)
  201. int    delim;
  202. char    *src, *map;
  203. {
  204.     /*    Expand the set pointed to by "*src" into the bitmap "map."
  205.      *    Stop at delim or end of string.  Update *src to point
  206.      *    at terminator.  A set can have one element {x} or several
  207.      *    elements ( {abcdefghijklmnopqrstuvwxyz} and {a-z}
  208.      *    are equivalent ).  Note that the dash notation is expanded
  209.      *    as sequential numbers.  This means (since we are using the
  210.      *    ASCII character set) that a-Z will contain the entire alphabet
  211.      *    plus the symbols: [\]^_'
  212.      *
  213.      *    The character classes are stored in a 16 byte wide bit field
  214.      *    where each bit corresponds to an ASCII character
  215.      */
  216.     
  217.     register int    first, last;
  218.     char    *start;
  219.     
  220.     start = src;
  221.     
  222.     while(  *src && *src != delim)
  223.     {
  224.         if( *src != '-')
  225.             setbit( esc( &src ), map );
  226.             
  227.         else if( src == start  || *(src + 1) == delim )
  228.             setbit ('-', map );
  229.             
  230.         else{
  231.             src++;
  232.             
  233.             if( *src < *(src - 2) )
  234.             {
  235.                 first = *src;
  236.                 last  = *(src - 2);
  237.             }
  238.             else
  239.             {
  240.                 first = *(src - 2);
  241.                 last  = *src;
  242.             }
  243.             
  244.             while( ++first <= last )
  245.                 setbit( first, map );
  246.                 
  247.             src++;
  248.         }
  249.     }
  250.     
  251.     return( src );
  252. }
  253.  
  254. /*----------------------------------------------------------------------*/
  255.  
  256. int    esc(s)
  257. char    **s;
  258. {
  259.     /* Map escape sequences into their equivalent symbols.  Returns the
  260.      * Correct ASCII character.  c is the character following the \.
  261.      */
  262.      
  263.     register int    rval;
  264.     
  265.     if( **s != ESCAPE )
  266.         rval = *( (*s)++ );
  267.     else
  268.     {
  269.         (*s)++;
  270.         
  271.         switch( toupper(**s) )
  272.         {
  273.         case '\0':    rval = ESCAPE;    break;
  274.         case 'B':    rval = '\b';    break;
  275.         case 'F':    rval = '\f';    break;
  276.         case 'N':    rval = '\n';    break;
  277.         case 'R':    rval = '\r';    break;
  278.         case 'S':    rval = ' ';    break;
  279.         case 'T':    rval = '\t';    break;
  280.         default:    rval = **s;    break;
  281.         }
  282.         
  283.         (*s)++;
  284.     }
  285.     
  286.     return (rval);
  287. }
  288.  
  289. /*----------------------------------------------------------------------*/
  290.  
  291. TOKEN    *getpat( arg )
  292. char    *arg;
  293. {
  294.     /*    Translate arg into a TOKEN string
  295.      */
  296.     
  297.     return ( makepat(arg, '\000' ) );
  298. }
  299.  
  300. /*----------------------------------------------------------------------*/
  301.  
  302. #ifdef    DEGUG
  303.  
  304. int    insert( ch, str )
  305. int        ch;
  306. register char    *str;
  307. {
  308.     /*    Insert ch into str at the place pointed to by str.  Move
  309.      *    everything else over a notch
  310.      */
  311.     
  312.     register char    *bp;
  313.     
  314.     bp = str;
  315.     
  316.     while (*str)            /* Find the end of the string    */
  317.         str++;
  318.         
  319.     do                /* Move the tail over one notch */
  320.     {
  321.         *(str + 1) = *str;
  322.         str--;
  323.         
  324.     } while (str >= bp);
  325.     
  326.     *bp = ch;            /* Put the char in the hole.    */
  327. }    
  328.  
  329. #endif
  330.  
  331. /*----------------------------------------------------------------------*/
  332.  
  333. int isalphanum(c)
  334. int    c;
  335. {
  336.     /*    Return true if c is a alphabetic character or digit,
  337.      *    flase otherwise.
  338.      */
  339.     
  340.     return ( ('a' <= c && c <= 'z') ||
  341.          ('A' <= c && c <= 'Z') ||
  342.          ('0' <= c && c <= '9')
  343.            );
  344. }
  345.  
  346. /*----------------------------------------------------------------------*/
  347.  
  348. TOKEN    *makepat(arg, delim)
  349. char    *arg;
  350. int    delim;
  351. {
  352.     /*    Make a pattern template from the string pointed to by arg.
  353.      *    Stop when delim or '\000' or '\n' is found in arg.
  354.      *    Return a pointer to the pattern template.
  355.      *
  356.      *    The pattern templates used here are somewhat different
  357.      *    than those ued in the book; each token is a structure
  358.      *    of the form TOKEN (see tools.h).  A token consists of 
  359.      *    an identifer, a ponter to a string, a literal
  360.      *    characte and a ponter to another token.  This last is 0 if
  361.      *    there is no subsequent token.
  362.      *
  363.      *    The one strangemess here is caused (again) by CLOSURE which
  364.      *    has to be put in front of the previous token.  To make this 
  365.      *    insertion a little easier, the 'nex' field of the last
  366.      *    token in the chain (the one pointed to by 'tail') is make
  367.      *    to point at the previous node.  When we are finished,
  368.      *    tail->next is set ot 0.
  369.      */
  370.     
  371.     TOKEN    *head, *tail;
  372.     TOKEN    *ntok;
  373.     int    error, i;
  374.     
  375.     /*    Check for characters that aren't legal at the beginning
  376.      *    of a template.
  377.      */
  378.     
  379.     if (*arg == '\0' || *arg == delim || *arg == '\n' || *arg == CLOSURE)
  380.         return(0);
  381.     
  382.     error = 0;
  383.     head  = 0;
  384.     tail  = 0;
  385.     
  386.     for(; *arg && *arg != delim && *arg != '\n' && !error; arg++)
  387.     {
  388.         ntok = (TOKEN *) malloc(TOKSIZE);
  389.         
  390.         if( error = !ntok )
  391.         {
  392.             fprintf(stderr,
  393.                 "Not enough memory for pattern template\n");
  394.             break;
  395.         }
  396.         
  397.         switch(*arg)
  398.         {
  399.         case ANY:
  400.             ntok->tok = ANY;
  401.             break;
  402.             
  403.         case BOL:
  404.             if (head == 0)    /* then this is the first symbol */
  405.                 
  406.                 ntok->tok = BOL;
  407.             else
  408.                 error = 1;
  409.             break;
  410.             
  411.         case EOL:
  412.             
  413.             if ( *(arg + 1) == delim || *(arg + 1) == '\0'
  414.                          || *(arg + 1) == '\n' )
  415.                 ntok->tok = EOL;
  416.             else
  417.                 error = 1;
  418.             break;
  419.             
  420.         case CCL:
  421.         
  422.             if (*(arg + 1) == NEGATE)
  423.             {
  424.                 ntok->tok = NCCL;
  425.                 arg += 2;
  426.             }
  427.             else
  428.             {
  429.                 ntok->tok =  CCL;
  430.                 arg++;
  431.             }
  432.             
  433.             if ( ntok->bitmap = (char *) calloc( 16, 1 ) )
  434.             {
  435.                 arg = dodash(CCLEND, arg, ntok->bitmap );
  436.             }
  437.             else
  438.             {
  439.                 fprintf(stderr,"Not enough memory for pat\n");
  440.                 error = 1;
  441.             }
  442.             
  443.             break;
  444.             
  445.         case CLOSURE:
  446.         
  447.              switch ( tail->tok )
  448.             {
  449.             case BOL:
  450.             case EOL:
  451.             case CLOSURE:
  452.                 return(0);
  453.             default:
  454.                 ntok->tok = CLOSURE;
  455.             }
  456.             break;
  457.             
  458.         default:
  459.             ntok->tok = LITCHAR;
  460.             ntok->lchar = esc( &arg );
  461.             --arg;    /* esc advances us past the character */
  462.             
  463.         }
  464.         
  465.         if ( error )
  466.         {
  467.             unmakepat(head);
  468.             return(0);
  469.         }
  470.         else if (head == 0)
  471.         {
  472.             /* This is the first node in the chain.
  473.              */
  474.             
  475.             ntok->next = 0;
  476.             head = tail = ntok;
  477.         }
  478.         else if( ntok->tok != CLOSURE)
  479.         {
  480.             /* Insert at end of list (after tail) */
  481.             
  482.             tail->next = ntok;
  483.             ntok->next = tail;
  484.             tail = ntok;
  485.         }
  486.         else if( head != tail )
  487.         {
  488.             /* More than one node in the chain. Insert the 
  489.              * CLOSURE node immediately in from of tail.
  490.              */
  491.              
  492.             (tail->next)->next = ntok;
  493.             ntok->next = tail;
  494.         }
  495.         else
  496.         {
  497.             /* Only one node in the chain, Insert the CLOSURE
  498.              * node at the head of the linked list.
  499.              */
  500.             
  501.             ntok->next = head;
  502.             tail->next = ntok;
  503.             head = ntok;
  504.         }
  505.     }
  506.     
  507.     tail->next = 0;
  508.     return (head);
  509.     
  510. }
  511.  
  512. /*----------------------------------------------------------------------*/
  513.  
  514. char    *matchs(line, pat, ret_endp)
  515. char    *line;
  516. TOKEN    *pat;
  517. int    ret_endp;
  518. {
  519.     /*
  520.      *    Compares line and pattern.  Line is a character string while
  521.      *    pat is a pattern template made by getpat().
  522.      *    Returns:
  523.      *         1. A zero of no match was found.
  524.      *        2. A pointer to the last character satisfying the
  525.      *           match if ret_endp is non-zero.
  526.      *        3. A pointer to the beginning of the matched string
  527.      *           if ret_endp is 0;
  528.      *
  529.      *    For example:
  530.      *
  531.      *        matchs ("1234567890", getpat("4[0-9]*7"),0);
  532.      *
  533.      *    will return a pointer to the '4', while
  534.      *
  535.      *        matchs ("1234567890", getpat("4[0-9]*7"),1);
  536.      *
  537.      *    will return a pointer to the '7'.
  538.      */
  539.     
  540.     char    *rval, *bptr;
  541.     
  542.     bptr = line;
  543.     
  544.     while (*line)
  545.     {
  546.         if ( (rval = amatch(line, pat, bptr)) == 0)
  547.         {
  548.             line++;
  549.         }
  550.         else
  551.         {
  552.             rval = ret_endp ? rval : line ;
  553.             break;
  554.         }
  555.     }
  556.     return (rval);
  557. }
  558.  
  559. /*----------------------------------------------------------------------*/
  560.  
  561. char    *stoupper(str)
  562. char    *str;
  563. {
  564.     /*
  565.      *    Map the entire string pointed to by str to upper case.
  566.      *    Return str.
  567.      */
  568.     
  569.     char    *rval;
  570.     
  571.     rval = str;
  572.     
  573.     while (*str)
  574.     {
  575.         if ( 'a' <= *str && *str <= 'z' )
  576.             *str -= ('a' - 'A');
  577.             
  578.         str++;
  579.     }
  580.     
  581.     return (rval);
  582. }
  583.  
  584. /*----------------------------------------------------------------------*/
  585.  
  586. int    omatch (linp, pat, boln)
  587. char    **linp, *boln;
  588. TOKEN    *pat;
  589. {
  590.     /*    Match one pattern element, pointed at by pat, with the
  591.      *    character at **limp.  Return non-zero on match.
  592.      *    Otherwise, return 0.  *limp is advanced to skip over the
  593.      *    matched character; it is not advanced on failure.  The
  594.      *    amound of the advance is 0 for patterns that match null
  595.      *    strings, 1 otherwise.  "boln" should point at the position
  596.      *    that will match a BOL token.
  597.      */
  598.      
  599.     register int    advance;
  600.     
  601.     advance = -1;
  602.     
  603.     if ( **linp )
  604.     {
  605.         switch ( pat->tok )
  606.         {
  607.         case LITCHAR:
  608.             if ( **linp == pat->lchar )
  609.                 advance = 1;
  610.             break;
  611.         
  612.         case BOL:
  613.             if ( *linp == boln )
  614.                 advance = 0;
  615.             break;
  616.         
  617.         case ANY:
  618.             if ( **linp != '\n' )
  619.                 advance = 1;
  620.             break;
  621.             
  622.         case EOL:
  623.             if ( **linp == '\n' )
  624.                 advance = 0;
  625.             break;
  626.         
  627.         case CCL:
  628.             if ( testbit( **linp, pat->bitmap ) )
  629.                 advance = 1;
  630.             break;
  631.             
  632.         case NCCL:
  633.             if ( !testbit(  **linp, pat->bitmap) )
  634.                 advance = 1;
  635.             break;
  636.             
  637.         default:
  638.             printf("omatch: can't happen\n");
  639.         }
  640.     }
  641.     
  642.     if (advance >= 0)
  643.         *linp += advance;
  644.         
  645.     return ( ++advance );
  646. }
  647.  
  648. /*----------------------------------------------------------------------*/
  649.  
  650. #ifdef DEBUG
  651.  
  652. int    pr_line(ln)
  653. register char    *ln;
  654. {
  655.     /*    Print out Ln, if a non-printing character is found, print
  656.      *    out its numerical value in the form "\0<hex number>".
  657.      *    Again, this is a debugging aid.  It lets you see what's
  658.      *    really on the line.
  659.      */
  660.     
  661.     for ( ; *ln ; ln++)
  662.     {
  663.         if ( (' ' <= *ln) && (*ln <= '~') )
  664.             putchar(*ln);
  665.         else
  666.         {
  667.             printf("\\0x%02x", *ln);
  668.             
  669.             if (*ln == '\n')
  670.                 putchar('\n'); 
  671.         }
  672.     }
  673. }
  674.  
  675. /*----------------------------------------------------------------------*/
  676.  
  677. int    pr_tok( head )
  678. TOKEN    *head;
  679. {
  680.     /*    Print out the pattern template (linked list of TOKENs)
  681.      *    pointed to by head.  This is a useful debugging aid.  Note
  682.      *    that pr_tok() just scans along the linked list, terminating
  683.      *    on a null pointer; so, you can't use pr_tok from inside
  684.      *    makepat() because tail->next points to the previous
  685.      *    node instead of being null.  Note that NEGATE or OR_SYM
  686.      *    are not listed because they won't occur in a template.
  687.      */
  688.      
  689.     register char    *str;
  690.     register int    i;
  691.     
  692.     for ( ; head ; head = head->next )
  693.     {
  694.         switch(head->tok)
  695.         {
  696.         case BOL:
  697.             str = "BOL";
  698.             break;
  699.         
  700.         case EOL:
  701.             str = "EOL";
  702.             break;
  703.             
  704.         case ANY:
  705.             str = "ANY";
  706.             break;
  707.             
  708.         case LITCHAR:
  709.             str = "LITCHAR";
  710.             break;
  711.             
  712.         case ESCAPE:
  713.             str = "ESCAPE";
  714.             break;
  715.             
  716.         case CCL:
  717.             str = "CCL";
  718.             break;
  719.             
  720.         case CCLEND:
  721.             str = "CCLEND";
  722.             break;
  723.             
  724.         case NCCL:
  725.             str = "NCCL";
  726.             break;
  727.             
  728.         case CLOSURE:
  729.             str = "CLOSURE";
  730.             break;
  731.             
  732.         default:
  733.             str = "**** unknown ****";
  734.         }
  735.         
  736.         printf("%-8s at: 0x%x,", str, head);
  737.         
  738.         if (head->tok == CCL || head->tok == NCCL)
  739.         {
  740.             printf("string (at 0x%x) =<", head->bitmap );
  741.             
  742.             for ( i = 0; i < 0x7f ; i++)
  743.                 if ( testbit( i, head->bitmap) )
  744.                     putchar(i);
  745.                     
  746.             printf(">, ");
  747.         }
  748.         
  749.         else if (head->tok  == LITCHAR)
  750.             printf("lchar = %c, ", head->lchar);
  751.             
  752.         printf("next = 0x%x\n", head->next);
  753.     }
  754.  
  755.     putchar('\n');
  756. }
  757.     
  758. #endif
  759.  
  760. /*----------------------------------------------------------------------*/
  761.  
  762. int    unmakepat(head)
  763. TOKEN    *head;
  764. {
  765.     /*    Free up the memory used for the token string    */
  766.     
  767.     register TOKEN    *old_head;
  768.     
  769.     while (head)
  770.     {
  771.         switch (head->tok)
  772.         {
  773.         case CCL:
  774.         case NCCL:
  775.             free(head->bitmap);
  776.             /* no break, fall through to default */
  777.             
  778.         default:
  779.             old_head = head;
  780.             head = head->next;
  781.             free(old_head);
  782.             break;
  783.         }
  784.     }
  785. }
  786.  
  787. /*----------------------------------------------------------------------*/
  788.  
  789. char    *index( c, str )
  790. char    *str;
  791. {
  792.     /*    Return true if c is in str.
  793.      */
  794.      
  795.     while ( *str )
  796.         if ( *str++ == c )
  797.             return str;
  798.     return 0;
  799. } 
  800.